//莱文斯坦距离算法是一种量化两个字符串之间差异的算法.
//莱文斯坦距离指的是由一个字符串转换为另一个字符串最少需要执行多少次编辑操作.
//编辑操作包括:插入,删除,替换

use std::cmp::min;
use std::time::Instant;

fn edit_distance(source: &str, target: &str) -> usize {
    //极端情况:空字符串到字符串的转换
    if source.is_empty() {
        return target.len();
    } else if target.is_empty() {
        return source.len();
    }

    //建立矩阵存储过程值
    let source_c = source.chars().count();
    let target_c = target.chars().count();
    let mut distance = vec![vec![0; target_c + 1]; source_c + 1];
    (1..=source_c).for_each(|i| distance[i][0] = i);
    (1..=target_c).for_each(|j| distance[0][j] = j);

    //存储过程值,取增\删\改中的最小步骤数
    for (i, cs) in source.chars().enumerate() {
        for (j, ct) in target.chars().enumerate() {
            let ins = distance[i + 1][j] + 1;
            let del = distance[i][j + 1] + 1;
            let sub = distance[i][j] + (cs != ct) as usize;
            distance[i + 1][j + 1] = min(min(ins, del), sub);
        }
    }
    //返回最后一行最后一列的值
    *distance.last().and_then(|d| d.last()).unwrap()
}

//优化版,使用一个vec来存储过程值
fn edit_distance2(source: &str, target: &str) -> usize {
    //极端情况:空字符串到字符串的转换
    if source.is_empty() {
        return target.len();
    } else if target.is_empty() {
        return source.len();
    }

    //distance 存储了到各种字符串的编辑距离
    let target_c = target.chars().count();
    let mut distance = (0..=target_c).collect::<Vec<_>>();
    for (i, cs) in source.chars().enumerate() {
        let mut substt = i;
        distance[0] = substt + 1;

        //不断组合计算各个距离
        for (j, ct) in target.chars().enumerate() {
            let dist = min(
                min(distance[j], distance[j + 1]) + 1,
                substt + (cs != ct) as usize,
            );
            substt = distance[j + 1];
            distance[j + 1] = dist;
        }
    }
    //最后一个距离值就是最终答案
    distance.pop().unwrap()
}

fn main() {
    let s_time = Instant::now();

    let source = "abce";
    let target = "adcf";
    let distance = edit_distance(source, target);
    println!("Distance between {source} and {target}: {distance}");

    let source = "bdfc";
    let target = "adcf";
    let distance = edit_distance(source, target);
    println!("Distance between {source} and {target}: {distance}");

    let source = "abced";
    let target = "adcf";
    let distance = edit_distance2(source, target);
    println!("Distance between {source} and {target}: {distance}");
    println!("Time cost: {:?}ms", s_time.elapsed().as_millis());
}
